package _03_recursion;

import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/5/31 - 20:44
 * 递归实现二分查找
 */
public class BinarySearchTest {
    @Test
    public void test() {
        int[] arr = {1,2,4,6,9,12};
        int i = binarySearch(4, arr);
        System.out.println(i);
    }

    /**
     * 封装方法
     * @param t 目标
     * @param arr 数组
     * @return
     */
    public int binarySearch(int t, int[] arr) {
        return foo(0, arr.length - 1, t, arr);
    }

    private int foo(int l, int r, int t, int[] arr) {
        if(l > r) {
            return -1;
        }
        int m = (l + r) >>> 1;
        if(t < arr[m]) {
            return foo(l, m - 1, t, arr);
        } else if(t > arr[m]) {
            return foo(m + 1, r, t, arr);
        } else {
            return m;
        }
    }
}
